拯救oibh总部
题目 拯救oibh总部
思路分析
主要是怎么处理这个读入
一个比较棘手的问题 如果读入的数据是没空格的 我们前面的经验是说使用字符数组存 然后用for(int i=0;i<n;i++) cin>>g[i]读入
但是字符数组不会自动补0 会变成这个样子
一种解决方法是 仍旧用字符数组读 然后手动加一圈
char g[N][N];
for(int i=1;i<=n;i++)
cin>>g[i]+1;
for(int i=0;i<=n+1;i++) {
g[i][0]=g[i][m+1]='0'; // 填充左右边界
}
for(int j=0;j<=m+1;j++) {
g[0][j] = g[n+1][j]='0'; // 填充上下边界
}
或者改成int数组
int g[N][N];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char s;cin>>s;
if(s=='0')
g[i][j]=0;
else
g[i][j]=1;
}
}
int g[N][N];
for(int i=1;i<=n;i++){
string line;
cin>>line;
for(int j=1;j<=m;j++){
g[i][j]=line[j-1]-'0';
}
}
要注意的是 换了int数组后 涉及判断的地方都得改成用0 而不是'0'
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
const int N=510;
char g[N][N];
bool st[N][N];
int n,m;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool isVaild(int x,int y){
return x>=0 && x<=n+1 && y>=0 && y<=m+1 && !st[x][y];
}
void bfs(int x,int y){
queue<PII> q;
q.push({x,y});
st[x][y]=true;
while(q.size()){
auto cur=q.front();q.pop();
int ux=cur.first,uy=cur.second;
for(int i=0;i<4;i++){
int nx=ux+dx[i],ny=uy+dy[i];
if(isVaild(nx,ny) && g[nx][ny]=='0'){
st[nx][ny]=true;
q.push({nx,ny});
}
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>g[i]+1;
for(int i=0;i<=n+1;i++) {
g[i][0]=g[i][m+1]='0'; // 填充左右边界
}
for(int j=0;j<=m+1;j++) {
g[0][j] = g[n+1][j]='0'; // 填充上下边界
}
// for(int i=0;i<=n+1;i++){
// for(int j=0;j<=m+1;j++)
// cout<<g[i][j]<<" ";
// cout<<endl;
// }
bfs(0,0);
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(g[i][j]=='0' && !st[i][j]){
cnt++;
}
}
}
cout<<cnt;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
const int N=510;
int g[N][N];
bool st[N][N];
int n,m;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool isVaild(int x,int y){
return x>=0 && x<=n+1 && y>=0 && y<=m+1 && !st[x][y];
}
void bfs(int x,int y){
queue<PII> q;
q.push({x,y});
st[x][y]=true;
while(q.size()){
auto cur=q.front();q.pop();
int ux=cur.first,uy=cur.second;
for(int i=0;i<4;i++){
int nx=ux+dx[i],ny=uy+dy[i];
if(isVaild(nx,ny) && g[nx][ny]==0){
st[nx][ny]=true;
q.push({nx,ny});
}
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char s;cin>>s;
if(s=='0')
g[i][j]=0;
else
g[i][j]=1;
}
}
// for(int i=0;i<=n+1;i++){
// for(int j=0;j<=m+1;j++)
// cout<<g[i][j]<<" ";
// cout<<endl;
// }
//
bfs(0,0);
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(g[i][j]==0 && !st[i][j]){
cnt++;
}
}
}
cout<<cnt;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
const int N=510;
int g[N][N];
bool st[N][N];
int n,m;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool isVaild(int x,int y){
return x>=0 && x<=n+1 && y>=0 && y<=m+1 && !st[x][y];
}
void bfs(int x,int y){
queue<PII> q;
q.push({x,y});
st[x][y]=true;
while(q.size()){
auto cur=q.front();q.pop();
int ux=cur.first,uy=cur.second;
for(int i=0;i<4;i++){
int nx=ux+dx[i],ny=uy+dy[i];
if(isVaild(nx,ny) && g[nx][ny]==0){
st[nx][ny]=true;
q.push({nx,ny});
}
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
string line;
cin>>line;
for(int j=1;j<=m;j++){
g[i][j]=line[j-1]-'0';
}
}
// for(int i=0;i<=n+1;i++){
// for(int j=0;j<=m+1;j++)
// cout<<g[i][j]<<" ";
// cout<<endl;
// }
//
bfs(0,0);
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(g[i][j]==0 && !st[i][j]){
cnt++;
}
}
}
cout<<cnt;
return 0;
}
💬 评论